/*
 * Copyright (C) 2006  Nicolas Normand
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */

#ifndef GRAPH_BASIC_H_
#define GRAPH_BASIC_H_

#include <vector>
#include <list>
#include <map>

namespace graph
{

namespace exception
{
	class unknown {};
	class vertex_out_of_range: virtual public unknown {};
	class vertex_not_found: virtual public unknown {};
	class edge_not_found: virtual public unknown {};
}

template <typename V, typename A>
class basic
{
	public:
	struct ltpair_i_i
	{
		bool operator() (const std::pair<int, int>& p1, const std::pair<int, int>& p2) const
		{
			if (p1.first < p2.first)
				return true;
			else if (p1.first == p2.first && p1.second < p2.second)
				return true;
			else
				return false;
		}
	};
	
	typedef std::map<std::pair<int, int>, A, ltpair_i_i> edge_t;
	
	protected:
	std::vector<V> vertexes__;
	edge_t edges__;

	public:
	// Constructors & destructor
	basic() {}
	basic(int n, const V initializator)
	{
		for (int i=0; i<n; i++)
			vertexes__.push_back(initializator);
	}
		

	virtual ~basic() {}

	// Basic accessors
	std::vector<V>& vertexes() { return vertexes__; }
	edge_t& edges() { return edges__; }


	// simple tests
	bool vertex_exist(int i)
	{
		return i >= 0 && (unsigned int)i < vertexes__.size();
	}

	bool vertex_exist(const V v)
	{
		for (unsigned int i=0; i<vertexes__.size(); i++)
			if (vertexes__[i] == v)
				return true;
		return false;
	}

	virtual bool edge_exist(const std::pair<int, int>& edge_) =0;

	virtual bool edge_exist(int first, int second)
	{
		return edge_exist(std::pair<int, int>(first, second));
	}

	// Advanced accessors
	V& vertex(int i)
	{
		if (vertex_exist(i))
			return vertexes__[i];
		else
			throw graph::exception::vertex_out_of_range();
	}

	virtual A& edge(const std::pair<int, int>& edge_) =0;

	virtual A& edge(int first, int second)
	{
		return edge(std::pair<int, int>(first, second));
	}


	// Complex accessors
	virtual std::list<int> successors(int vertex)
	{
		std::list<int> ls;
		
		typename edge_t::iterator it = edges__.begin();
		while (it != edges__.end())
		{
			if (it->first.first == vertex)
				ls.push_back(it->first.second);
			it++;
		}
		return ls;
	}

	virtual std::list<int> predecessors(int vertex)
	{
		std::list<int> lp;

		typename edge_t::iterator it = edges__.begin();
		while (it != edges__.end())
		{
			if (it->first.second == vertex)
				lp.push_back(it->first.first);
			it++;
		}
		return lp;
	}

	virtual int getIndex(const V data)
	{
		unsigned int i = 0;
		while (i < vertexes__.size())
		{
			if (vertexes__[i] == data)
				return (signed)i;
			i++;
		}
		throw exception::vertex_not_found();
	}
	
	
	// Add operators
	void new_vertex(const V data)
	{
		vertexes__.push_back(data);
	}
	void new_vertexes(int n, const V data)
	{
		for (int i=0; i<n; i++)
			new_vertex(data);
	}
	
	virtual void new_edge(int first, int second, const A data) =0;


	// Erasing operators
	virtual void delete_edge(int first, int second) =0;
	virtual void delete_edge(const std::pair<int, int>& edge_)
	{
		delete_edge(edge_.first, edge_.second);
	}
};

} // End of: namespace

#endif

